package no27;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/20 15:17
 * II 回文链表
 * https://leetcode.cn/problems/aMhZSa/
 */
public class Solution01 {

    // 反转一半的链表 时间复杂度 O(n), 空间复杂度 O(1)
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 处理只有两个节点的情况
        if (head.next.next == null) {
            return head.val == head.next.val;
        }
        // 快慢指针, 找到中间位置
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 此时 slow 指向的位置为链表中间靠前一个的位置, fast 指向链表的尾部
        // 或者 slow 指向位置为链表的中间节点, fast 指向链表的最后一个节点
        // 将该位置后的链表局部反转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next; // 先记录当前节点的后一个位置
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 此时 slow 指向链表的最后一个节点, 同时, 后半部分链表已经逆置
        cur = head;
        while (cur != slow && cur.next != slow) {
            if (cur.val != slow.val) {
                return false;
            }
            cur = cur.next;
            slow = slow.next;
        }
        // 处理可能剩下的最后节点(原链表为偶数个节点)
        if (cur.next == slow) {
            return cur.val == slow.val;
        }
        return true;
    }

    // 时间复杂度 O(n), 空间复杂度 O(n)
    // 使用栈模拟
    public boolean isPalindrome2(ListNode head) {
        // 遍历两次 + 栈 进行匹配
        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }


    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
